<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>1807：[Ioi2007]Pairs 彼此能听得见的动物对数
</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Ioi2007]Pairs 彼此能听得见的动物对数
</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Ioi2007]Pairs 彼此能听得见的动物对数
</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Ioi2007]Pairs 彼此能听得见的动物对数
                </h1>
                <p>时间限制：20s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：64MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p>Mirko 和 Slavko 正在玩动物玩具的游戏。 首先，他们要在下图给出的三种玩具模板中选择一种。三种模板分别由一维、二维和三维的网格点（在图中用圆圈表示）组成。

<img border="0" src="../file/1807_0.jpg"> 
 
接下来Mirko 把 N 个小动物玩具放到选中的模板的网格点上。
动物玩具可以走一步到达与它相邻的网格点上（在图中相邻的点之间有一条小短线相连）。两个网格点之间的距离定义为从一个网格点到另一个网格点所需要移动的最小步数。
如果两个动物之间的距离小于等于D，则它们之间可以互相听见。Slavko 的任务是计算在模板上有多少对动物可以互相听得见。
任务
给定模板的类型、所有动物的位置以及数字D，写一个程序计算有多少对动物可以互相听得见。
</p><hr/><h3>输入格式</h3><p>输入的第一行按顺序给出四个整数：
&#8226; 模板类型 B (1 ≤ B ≤ 3);
&#8226; 玩具动物的数目 N (1 ≤ N ≤ 100 000);
&#8226; 动物之间可以互相听得见的最大距离D (1 ≤ D ≤ 100 000 000);
&#8226; 模板的大小 M ( 即在输入中允许的最大的坐标值):
&#61607; 当 B=1 时, M 最大是 75 000 000.
&#61607; 当 B=2时, M 最大是 75 000.
&#61607; 当 B=3时, M 最大是 75.
接下来的N 行每行包含B 个整数，整数之间用空格隔开，表示一个动物玩具的坐标。坐标的取值范围是1 到 M ( 包括M )。
每个网格点可以同时包含多个动物玩具。
</p><hr/><h3>输出格式</h3><p>输出应该包括一个整数，表示可以互相听得见的玩具动物的对数。
注意：使用64 位整数类型计算和输出结果 (在 C/C++ 中用long long, 在Pascal 中用int64 ) 。

评分
在30分的测试数据中, 动物数目 N 最多是 1 000。
如果成功通过了某一种模板（一维、二维或者三维）的全部测试数据，将会得到至少30分。
</p><hr/><h3>样例输入</h3><pre>input 1
1 6 5 100 
25 
50 
50 
10 
20 
23 

input 2
2 5 4 10 
5 2 
7 2 
8 4 
6 5 
4 4 
</pre><hr/><h3>样例输出</h3><pre>output 1
4 

output 2 
8 </pre><hr/><h3>提示</h3><p>对于input 1的解释： 假设动物按给出的顺序编号为1到6。4对互相能够听得到的动物分别是:
&#8226; 1-5 ( 距离是5)
&#8226; 1-6 ( 距离是2)
&#8226; 2-3 ( 距离是0)
&#8226; 5-6 ( 距离是3)
对于input 2 的解释：8对动物分别是:
&#8226; 1-2 ( 距离是2)
&#8226; 1-4 ( 距离是4)
&#8226; 1-5 ( 距离是3)
&#8226; 2-3 ( 距离是3)
&#8226; 2-4 ( 距离是4)
&#8226; 3-4 ( 距离是3)
&#8226; 3-5 ( 距离是4)
&#8226; 4-5 ( 距离是3)
</p><hr/><h3>题目来源</h3><p>Day2</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=1807" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1807" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>